package com.data_structure_algorithm.data_structure.linked;

import java.util.Objects;

/**
 * @author 何章怀晓 hezhanghuaixiao
 * @version V1.0
 * @desc 环形链表
 */
public class CireleLinked {
  //创建环形链表

  Nodes first;


  public void add(Nodes node) {
    if (Objects.isNull(node)) {
      return;
    }
    //辅助指针
    Nodes temp = null;

    if (Objects.isNull(first)) {
      //说明是首节点
      first = node;//first指针
      node.next = first; //环

    }
    temp = first;//first不能动，temp是辅助节点

    while (true) {
      if (temp.next == first) {
        break;
      }

      temp = temp.next;
    }

    //添加操作
    //temp此时是队尾节点
    //将node添加到temp和first之间
    temp.next = node;
    node.next = first;

  }

  public void bianli(Nodes nodes) {
    if (Objects.isNull(nodes)) {
      return;
    }

    Nodes temp = first;

    while (true) {

      System.out.println("Node信息为：id -->" + temp.id);

      if (temp.next == first) {
        break;

      }

      temp = temp.next;
    }

  }


  /**
   * @param startNum 开始节点
   * @param countNum 数几次
   * @return void
   * @describe
   * @author 何章怀晓 hezhanghuaixiao
   * @date 2022/3/21  22:04
   * @other
   */
  public void countNum(int startNum, int countNum) {

    //小孩出队顺序
    //思路 在首次报数节点之前，创建helper辅助指针，每数一次，helper和first均向后移动1次（这里1次代表数2下，首节点也算一次，如从1开始数2次，是 1 - 2 ）
    //    helper和first配合将节点移除
    //要求：N个节点， 从第startNum个开始报数， 每次数countNum下 ，每轮数到countNum位置的节点出圈，求出局次序
    Nodes helper = first;

    //先找到first的前一个节点
    while (true) {
      if (helper.next == first) {
        break;
      }
      helper = helper.next;
    }

    //初始first应移动到startNum - 1 的位置(如从20开始，那么首节点在1的地方，需移动19次即20-1)，helper紧随其后

    //helper在first的前面，helper移动startNum次即到了既定位置，next就是first
    for (int i = 1; i < startNum; i++) {
      //helper移动
      helper = helper.next;
    }
    //first和helper的位置已确定
    first = helper.next;
    //开始出队

    while (true) {

      if (first == helper) {

        System.out.println("最终留下的节点--------------" + helper.id + "----------------");

        break;
      }
      //每次first和helper移动countNum-1次，此时first的位置就是要出队的位置
      for (int i = 1; i < countNum /*   <  countNum-1次*/; i++) {
        helper = helper.next;
      }
      //helper进入指定位置，下个节点是first,将first移动到指定位置;first 现在在出局节点的位置
      first = helper.next;

      //本轮出圈节点
      Nodes out = first;

      System.out.println("出队顺序--------------" + out.id + "----------------");
      //first位置出队，需将first后移，让出位置  而后让helper的next指向first即可
      first = first.next;

      helper.next = first;
    }

    //System.out.println(helper.id + "---------");
  }


  public static void main(String[] args) {
    CireleLinked cireleLinked = new CireleLinked();

    for (int i = 1; i <= 5; i++) {
      cireleLinked.add(new Nodes(i));
    }

    //cireleLinked.bianli(cireleLinked.first);
    cireleLinked.countNum(1, 2);
  }

}


class Nodes {

  int id;

  Nodes next;

  public Nodes(int id) {
    this.id = id;
  }


  @Override
  public String toString() {
    return "Nodes{" +
        "id=" + id +
        '}';
  }
}
